package Year22_Month04.day19;

public class MyLinkedList {

    static class ListNode{
        int value;//定义每个节点的值
        ListNode prev;//定义前节点
        ListNode next;//定义后节点
        public ListNode(int e){
            value = e;
        }
    }
    int size;//定义链表的节点长
    ListNode head;//定义一个虚拟头节点
    ListNode tail;//定义一个虚拟尾结点

    public MyLinkedList(){
        size = 0;
    }

    public int get(int index) {
        //先判断index是否合理
        if(index < 0 || index > size - 1){
            return -1;
        }
        int count = 0;
        ListNode tmp = head;
        //合理的话就再往下走
        while(count < index){
            tmp = tmp.next;
            count++;
        }
        return tmp.value;
    }

    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        //这里先判断一下元素是否为空，如果为空就是首尾元素都指向一个节点
        if(size == 0){
            tail = node;
        }else{
            //如果不为空那就把新的节点设置为头结点
            node.next = head;
            head.prev = node;
        }
        head = node;
        size++;
    }
    //这里的思路和头插法一致
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        if(size == 0){
            head = node;
        }else{
            tail.next = node;
            node.prev = tail;
        }
        tail = node;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if(index <= 0){
            addAtHead(val);
        }else if(index == size){
            addAtTail(val);
        }else if(index > size){
            return;
        }else{
            //这里的话就不构造虚拟节点了，就直接从头结点开始遍历，然后直接插到对应节点的头结点就好
            int count = 0;
            ListNode tmp = head;
            ListNode node = new ListNode(val);
            while(count < index){
                tmp = tmp.next;
                count++;
            }
            //插入节点的话就要先处理待插入的节点，不能动原节点
            node.next = tmp;
            node.prev = tmp.prev;
            //这里的话就开始对原节点开始处理
            tmp.prev.next = node;
            tmp.prev = node;
            size++;
        }
    }

    public void deleteAtIndex(int index) {
        if(index >= size || index < 0){
            return;
        }
        if(index == 0){
            head = head.next;
        }else if(index == size - 1){
            tail = tail.prev;
        }else{
            ListNode tmp = head;
            int count = 0;
            while(count < index){
                count++;
                tmp = tmp.next;
            }
            tmp.prev.next  = tmp.next;
            tmp.next.prev = tmp.prev;
        }
        size--;
    }
}
